/**
 * @file arbre.c
 * @brief implémentation de l'arbre
 */
#include "arbre.h"
#include <unistd.h>
#define TAILLE_TAB 2
#define LARGEUR_MAX 80

/** 
 * Crée un noeud avec les paramètres passés en arguments
 */
Noeud *creerNoeud(const int i, const Operande operande);

/**
 * Initialise un noeud avec les paramètres passés en arguments
 */
void initNoeud(Noeud *noeud, const int i, const Operande operande);

/**
 * Détruit le noeud passé en argument
 */
void detruireNoeud(Noeud *noeud);

/**
 * Initialise une copie du noeud passé en argument
 */
void initNoeudCopie(Noeud **noeudDest, const Noeud *noeudSource);

/**
 * Retourne la valeur du noeud passé en argument
 */
double valeurNoeud(const Noeud *noeud);

/**
 * Retourne la prochaine expression rencontrée dans l'expression passsée en argument.
 */
Noeud *lit_expression(const char **expression);

/**
 * Retourne le prochain terme rencontré dans l'expression passée en argument.
 */
Noeud * lit_terme(const char **expression);

/**
 * Retourne le prochain facteur rencontré dans l'expression passée en argument.
 */
Noeud *lit_facteur(const char **expression);

/**
 * Retourn le prochain opérateur dans l'expression passée en argument.
 */
Operande lit_operateur(const char **expression);

/**
 * Retourne vrai si l'expression passée en argument est une addition.
 */
int est_addition(const char *expression);

/**
 * Retourne vrai si l'expression passée en argument est un facteur.
 */
int est_facteur(const char *expression);

/**
 * Retourne vrai si l'expression passée en argument est une paranthèse ouvrante et si oui la supprime.
 */
int est_parenthese_ouvrante(const char **expression);

/**
 * Lit l'expression passée en argument et supprime la paranthèse fermante.
 */
void lit_parenthese_fermante(const char **expression);

/**
 * Lit l'expression passée en argument et supprime la constante. 
 */
int lit_constante(const char **expression);

/**
 * Affiche l'arborescence du noeud sous forme d'expression mathématique.
 */
void afficheNoeudExpression(const Noeud *noeud);

/**
 * Retourne vrai si le noeud passé en argument est un produit. 
 */
int verificationProduitNoeud(const Noeud *noeud);

/**
 *  Retourne vrai si le noeud passé en argument est une addition.
 */
int verificationAdditionNoeud(const Noeud *noeud);

/**
 *  Développe le produit du noeud passé en argument.
 */
void developpeProduitNoeud(const Noeud *noeud, Noeud **noeudDev);

/**
 *  Développe l'addition du noeud passé en argument.
 */
void developpeAdditionNoeud(const Noeud *noeud1, const Noeud *noeud2, Noeud ** noeudDev);

/**
 *  Retourne la profondeur du fils passé en argument.
 */
int hauteurMaxFils(const Noeud *noeud);

/**
 * Retourne le nombre de caractère de chaque sous noeud
 */
void nombreSousNoeud(const Noeud *noeud, int *nbMax);

void initArbreVide(Arbre *arbre)
{
  if(arbre != NULL)
    {
      arbre->adRacine = NULL;
    }
  else
    {
      fprintf(stderr, "L'arbre n'est pas déclaré\n");
      exit(1);
    }
}

void initArbreEntier(Arbre *arbre, const int i)
{
  initArbreVide(arbre);
  arbre->adRacine = creerNoeud(i, valeur);
}

void initArbreCopie(Arbre *arbreDest, const Arbre *arbreSource)
{
  if(arbreDest != NULL)
    {
      initNoeudCopie(&(arbreDest->adRacine), arbreSource->adRacine);
    }
  else
    {
      fprintf(stderr, "L'arbre de destination n'a pas été déclarer\n");
      exit(1);
    }
}

void initArbreExpression(Arbre *arbre, const char *expression)
{
  if(arbre != NULL)
    {
      arbre->adRacine = lit_expression(&expression);
    }
  else
    {
      fprintf(stderr, "L'arbre n'a pas été déclarer\n");
      exit(1);
    }
}

void initNoeudCopie(Noeud **noeudDest, const Noeud *noeudSource)
{
  (*noeudDest) = creerNoeud(noeudSource->element, noeudSource->operande);
  prems_Ens(noeudSource->ensemble);
  while(noeudSource->ensemble->courant != NULL)
    {
      Noeud *noeudFils = NULL;

      initNoeudCopie(&noeudFils, getData_Ens(noeudSource->ensemble));
      insert_Ens((*noeudDest)->ensemble, noeudFils, NULL);
      suivant_Ens(noeudSource->ensemble);
    }
}

void initNoeud(Noeud *noeud, const int i, const Operande operande)
{
  if(noeud != NULL)
    {
      noeud->element = i;
      noeud->operande = operande;
      noeud->ensemble = creer_Ens();
    }
  else
    {
      fprintf(stderr, "Le noeud n'est pas déclaré\n");
      exit(1);
    }
}

Noeud *creerNoeud(const int i, const Operande operande)
{
  Noeud *noeud = NULL;
  noeud = (Noeud *) malloc (sizeof(Noeud));
  if(noeud == NULL)
    {
      fprintf(stderr, "Erreur malloc noeud\n");
      exit(1);
    }
  initNoeud(noeud, i, operande);
  return noeud;
}

void detruireNoeud(Noeud *noeud)
{
  if(noeud != NULL)
    {
      prems_Ens(noeud->ensemble);
      while(noeud->ensemble->courant != NULL)
	{
	  detruireNoeud(getData_Ens(noeud->ensemble));
	  suivant_Ens(noeud->ensemble);
	}
      detruire_Ens(&(noeud->ensemble), NULL);
      free(noeud);
    }
}

void detruireArbre(Arbre *arbre)
{
  detruireNoeud(arbre->adRacine);
  arbre->adRacine = NULL;
}

void operandeNoeud(const Noeud *noeudA, const Noeud *noeudB, Noeud **noeudR, Operande operande)
{
  Noeud *noeudF = NULL;
  (*noeudR) = creerNoeud(0, operande);
  if(noeudA->operande == noeudB->operande && noeudA->operande == operande)
    {
      prems_Ens(noeudA->ensemble);
      while(noeudA->ensemble->courant != NULL)
	{
	  initNoeudCopie(&noeudF, getData_Ens(noeudA->ensemble));
	  insert_Ens((*noeudR)->ensemble, noeudF, NULL);
	  suivant_Ens(noeudA->ensemble);
	}
      prems_Ens(noeudB->ensemble);
      while(noeudB->ensemble->courant != NULL)
	{
	  initNoeudCopie(&noeudF, getData_Ens(noeudB->ensemble));
	  insert_Ens((*noeudR)->ensemble, noeudF, NULL);
	  suivant_Ens(noeudB->ensemble);
	}
    }
  else if(noeudB->operande == operande)
    {
      prems_Ens(noeudB->ensemble);
      while(noeudB->ensemble->courant != NULL)
	{
	  initNoeudCopie(&noeudF, getData_Ens(noeudB->ensemble));
	  insert_Ens((*noeudR)->ensemble, noeudF, NULL);
	  suivant_Ens(noeudB->ensemble);
	}
      initNoeudCopie(&noeudF, noeudA);
    }
  else if(noeudA->operande == operande)
    {
      prems_Ens(noeudA->ensemble);
      while(noeudA->ensemble->courant != NULL)
	{
	  initNoeudCopie(&noeudF, getData_Ens(noeudA->ensemble));
	  insert_Ens((*noeudR)->ensemble, noeudF, NULL);
	  suivant_Ens(noeudA->ensemble);
	}
      initNoeudCopie(&noeudF, noeudB);
    }
  else
    {
      initNoeudCopie(&noeudF, noeudA);
      insert_Ens((*noeudR)->ensemble, noeudF, NULL);
      initNoeudCopie(&noeudF, noeudB);
      insert_Ens((*noeudR)->ensemble, noeudF, NULL);
    }
}

void additionArbres(const Arbre *arbreA, const Arbre *arbreB, Arbre *arbreR)
{
  Noeud *noeud = NULL;
  operandeNoeud(arbreA->adRacine, arbreB->adRacine, &noeud, addition);
  arbreR->adRacine = noeud;
}

void multiplicationArbres(const Arbre *arbreA, const Arbre *arbreB, Arbre *arbreR)
{
  Noeud *noeud = NULL;
  operandeNoeud(arbreA->adRacine, arbreB->adRacine, 
		&noeud, multiplication);
  arbreR->adRacine = noeud;
}


void soustractionArbres(const Arbre *arbreA, const Arbre *arbreB, Arbre *arbreR)
{
  Noeud *noeud = NULL;
  operandeNoeud(arbreB->adRacine, arbreA->adRacine, 
		&noeud, soustraction);
  arbreR->adRacine = noeud;
}

void divisionArbres(const Arbre *arbreA, const Arbre *arbreB, Arbre *arbreR)
{
  Noeud *noeud = NULL;
  operandeNoeud(arbreA->adRacine, arbreB->adRacine, 
		&noeud, division);
  arbreR->adRacine = noeud;
}

double valeurArbre(const Arbre *arbre)
{
  return valeurNoeud(arbre->adRacine);
}

double valeurNoeud(const Noeud *noeud)
{
  double ret = 0;
  switch(noeud->operande)
    {
    case valeur :
      return noeud->element;
      break;
    case addition :

      prems_Ens(noeud->ensemble);
      while(noeud->ensemble->courant != NULL)
	{
	  ret += valeurNoeud(getData_Ens(noeud->ensemble));
	  suivant_Ens(noeud->ensemble);
	}
      return ret;
    case multiplication :
      ret = 1;
      prems_Ens(noeud->ensemble);
      while(noeud->ensemble->courant != NULL)
	{
	  ret *= valeurNoeud(getData_Ens(noeud->ensemble));
	  suivant_Ens(noeud->ensemble);
	}
      return ret;
    case soustraction :
      prems_Ens(noeud->ensemble);
      ret = valeurNoeud(getData_Ens(noeud->ensemble));
      suivant_Ens(noeud->ensemble);
      while(noeud->ensemble->courant != NULL)
	{
	  ret -= valeurNoeud(getData_Ens(noeud->ensemble));
	  suivant_Ens(noeud->ensemble);
	}
      return ret;
    case division :
      ret = 1;
      prems_Ens(noeud->ensemble);
      ret = valeurNoeud(getData_Ens(noeud->ensemble));
      suivant_Ens(noeud->ensemble);
      while(noeud->ensemble->courant != NULL)
	{
	  double i = valeurNoeud(getData_Ens(noeud->ensemble));
	  if(i != 0)
	    ret /= i;
	  suivant_Ens(noeud->ensemble);
	}
      return ret;
    default :
      break;
    }
  return 0;
}

Noeud *lit_expression(const char **expression)
{
  Noeud *noeud1 = NULL;
  Noeud *noeud2 = NULL;
  Operande operande;
  noeud1 = lit_terme(expression);
  while(est_addition((*expression)))
    {
      Noeud *noeud3 = NULL;
      operande = lit_operateur(expression);
      noeud2 = lit_terme(expression);
      operandeNoeud(noeud1, noeud2, &noeud3, operande);
      detruireNoeud(noeud1);
      detruireNoeud(noeud2);
      return noeud3;
    }
  return noeud1;
}

Noeud * lit_terme(const char **expression)
{
  Noeud *noeud1 = NULL;
  Noeud *noeud2 = NULL;
  Operande operande;
  noeud1 = lit_facteur(expression);
  while(est_facteur((*expression)))
    {
      Noeud *noeud3 = NULL;
      operande = lit_operateur(expression);
      noeud2 = lit_facteur(expression);
      operandeNoeud(noeud1, noeud2, &noeud3, operande);
      detruireNoeud(noeud1);
      detruireNoeud(noeud2);
      return noeud3;
    }
  return noeud1;
}

Noeud *lit_facteur(const char **expression)
{
  Noeud *noeud;
  int constante;

  if(est_parenthese_ouvrante(expression))
    {
      noeud = lit_expression(expression);
      lit_parenthese_fermante(expression);
    }
  else
    {
      constante = lit_constante(expression);
      noeud = creerNoeud(constante, valeur);
    }
  return noeud;
}

Operande lit_operateur(const char **expression)
{
  Operande operande = valeur;
  char *endptr = NULL;
  while(*(*expression) == ' ')
    (*expression) ++;
  (void) strtol((*expression), &endptr, 10);
  if((*expression) == endptr)
    {
      switch((*expression)[0])
	{
	case '*':
	  operande = multiplication;
	  (*expression) ++;
	  break;
	case '/':
	  operande = division;
	  (*expression) ++;
	  break;
	case '+':
	  operande = addition;
	  (*expression) ++;
	  break;
	case '-':
	  operande = soustraction;
	  (*expression) ++;
	  break;
	}
    }
  return operande;
}

int est_addition(const char *expression)
{
  char *endptr = NULL;
  while((*expression) == ' ')
    expression ++;
  (void)strtol(expression, &endptr, 10);
  if(expression == endptr)
    {
      if(expression[0] == '+' || expression[0] == '-')
	return 1;
    }
  return 0;
}

int est_facteur(const char *expression)
{
  char *endptr = NULL;
  while((*expression) == ' ')
    expression ++;
  (void)strtol(expression, &endptr, 10);
  if(expression == endptr)
    {
      if(expression[0] == '*' || expression[0] == '/')
	return 1;
    }
  return 0;
}

int est_parenthese_ouvrante(const char **expression)
{
  while((*expression)[0] == ' ')
    (*expression) ++;
  if((*expression)[0] == '(')
    {
      (*expression)++;
      return 1;
    }
  return 0;
}

void lit_parenthese_fermante(const char **expression)
{
  while((*expression)[0] != ')')
    (*expression) ++;
  (*expression) ++;
}

int lit_constante(const char **expression)
{
  int ret;
  char *endptr = NULL;
  ret = strtol((*expression), &endptr, 10);
  if((*expression) == endptr)
    (*expression) = '\0';
  else
    (*expression) = endptr;
  return ret;
}

char getCaractereOperande(const Noeud* noeud)
{
  switch(noeud->operande)
    {
    case addition:
      return '+';
      break;
    case multiplication:
      return '*';
      break;
    case soustraction:
      return '-';
      break;
    case division:
      return '/';
      break;
    default:
      return '0';
    }
}

int poidElement(const Noeud *noeud)
{
  int ret = 1;
  if(noeud->operande == valeur)
    {
      FILE *f = NULL;
      f = fopen("/dev/null", "w");
      ret = fprintf(f,"%d", noeud->element);
      fclose(f);
    }
  return ret;
}

void nombreSousNoeud(const Noeud *noeud, int *nbMax)
{
  int tailleEl;

  tailleEl = poidElement(noeud) + 2;
  if(getTaille_Ens(noeud->ensemble) == 0)
    {
      if((*nbMax) < tailleEl)
	(*nbMax) = tailleEl;
      return;
    }
  prems_Ens(noeud->ensemble);
  while(noeud->ensemble->courant != NULL)
    {
      nombreSousNoeud(getData_Ens(noeud->ensemble), nbMax);
      suivant_Ens(noeud->ensemble);
    }
}

/**
 * Noeud à traiter
 */
int hauteurMaxFils(const Noeud *noeud)
{
  Ensemble *ens = noeud->ensemble;
  int tailleMax = 0;
  prems_Ens(ens);

  /* Parcours de tout les fils */
  while(ens->courant != NULL)
    {
      int taille = hauteurMaxFils(getData_Ens(ens));
      if(taille > tailleMax)
	tailleMax = taille;
      suivant_Ens(ens);
    }

  return tailleMax + 1;
}

void afficheNoeud(const Noeud *noeud, const int niveau, const int niveauAffiche, const int espaceCube)
{
  /* Variables */
  int nbFils;
  int nbEspace;
  int j;
  int i;
  Ensemble *ens = noeud->ensemble;
  int nbEspaceAff;

  /* Recupération de nombre de noeud dans chaque fils */
  nbFils = getTaille_Ens(ens);
  if(nbFils == 0)
    {
      for(i = 0; i < espaceCube * 4; i++)
	printf(" ");
      return ;
    }
  prems_Ens(ens);

  if(niveau < niveauAffiche)
    {
      for(i = 0, prems_Ens(ens); i < nbFils && ens->courant != NULL; 
	  i++, suivant_Ens(ens))
	{
	  afficheNoeud(getData_Ens(ens), niveau + 1, niveauAffiche, 
		       espaceCube);
	}
      /* Pour combler l'espace entre le noeud pere et les noeuds fils */
      return;
    }

  /* Placement des fils */
  for(i = 0, prems_Ens(ens); i < nbFils && ens->courant != NULL;
      i++, suivant_Ens(ens))
    {
      Noeud *noeudTmp = getData_Ens(ens);
      nbEspace = espaceCube - poidElement(noeudTmp);

      for(j = 0; j < nbEspace; j++)
	{
	  printf("%s", (i == 0 ? " " : "~"));
	  nbEspaceAff ++;
	}
      
      if(noeudTmp->operande == valeur)
	printf("%d", noeudTmp->element);
      else
	printf("%c", getCaractereOperande(noeudTmp));

      for(j = 0; j < espaceCube - 1; j++)
	{
	  printf("%s", (i < nbFils-1 ? "~" : " "));
	  nbEspaceAff ++;
	}

      if(i < nbFils-1)
	{
	  printf("|");
	}
      else
	printf(" ");

    }
}

void afficheArbre(const Arbre *arbre)
{
  /* Variables */
  int nbFils;
  int nbNoeudTotal = 0;
  int hauteur;
  int i;
  Ensemble *ens = arbre->adRacine->ensemble;
  int maxNoeudFils = 0;
  int nbEspace;
  /* Affichage du noeud principal */
  nbFils = getTaille_Ens(ens);
  /* Recupération de nombre de noeud dans chaque fils */
  prems_Ens(ens);
  i = 0;
  for(i = 0, prems_Ens(ens); ens->courant != NULL && i < nbFils; 
      i++, suivant_Ens(ens))
    {
      nombreSousNoeud(getData_Ens(ens), &maxNoeudFils);
    }
  hauteur = hauteurMaxFils(arbre->adRacine);
  
  nbEspace = maxNoeudFils;
  for(i = 0; i < hauteur - 1; i++)
    nbEspace *= 2;
  for(i = 0; i < nbEspace - 1; i++)
    printf(" ");

  if(arbre->adRacine->operande == valeur)
    printf("%d\n", arbre->adRacine->element);
  else
    printf("%c\n", getCaractereOperande(arbre->adRacine));

  if(maxNoeudFils * nbFils < nbNoeudTotal)
    maxNoeudFils ++;
  for(i = 1; i < hauteur; i++)
    {
      
      for(prems_Ens(ens); ens->courant != NULL; suivant_Ens(ens))
	{
	  int j;
	  nbEspace = maxNoeudFils;
	  for(j = 0; j < hauteur - i - 1; j ++)
	    {
	      nbEspace *= 2;
	    }
	  afficheNoeud(arbre->adRacine, 1, i, nbEspace);

	}
      printf("\n");
    }
}

void afficheArbreExpression(const Arbre *arbre)
{
  afficheNoeudExpression(arbre->adRacine);
}


void afficheNoeudExpression(const Noeud *noeud)
{
  prems_Ens(noeud->ensemble);
  while(noeud->ensemble->courant != NULL)
    {
      Noeud *noeudE = getData_Ens(noeud->ensemble);
      if(noeudE->operande == valeur)
	printf("%d ", noeudE->element);
      else
	{
	  printf("( ");
	  afficheNoeudExpression(noeudE);
	  printf(") ");
	}
      suivant_Ens(noeud->ensemble);
      if(noeud->ensemble->courant != NULL)
	{
	  switch(noeud->operande)
	    {
	    case multiplication :
	      printf("* ");
	      break;
	    case addition :
	      printf("+ ");
	      break;
	    case soustraction :
	      printf("- ");
	      break;
	    case division :
	      printf("/ ");
	      break;
	    default :
	      printf("%d ", noeud->element);
	      break;
	    }
	}
    }
}

void developpeProduitArbre(const Arbre *arbre, Arbre *arbreDev)
{
  if(verificationProduitNoeud(arbre->adRacine))
    {
      developpeProduitNoeud(arbre->adRacine, &(arbreDev->adRacine));
    }
  else
    {
      initArbreCopie(arbreDev, arbre);      
    }
}

void developpeProduitNoeud(const Noeud *noeud, Noeud **noeudDev)
{
  Noeud *noeudTmp = NULL;
  Noeud *noeudTmp2 = NULL;
  Item *sauvegarde = NULL;

  (*noeudDev) = creerNoeud(0, addition);
  prems_Ens(noeud->ensemble);
  while(noeud->ensemble->courant != NULL)
    {
      noeudTmp = getData_Ens(noeud->ensemble);
      suivant_Ens(noeud->ensemble);
      sauvegarde = noeud->ensemble->courant;
      while(noeud->ensemble->courant != NULL)
	{
	  noeudTmp2 = getData_Ens(noeud->ensemble);
	  developpeAdditionNoeud(noeudTmp, noeudTmp2, noeudDev);
	  suivant_Ens(noeud->ensemble);
	}
      noeud->ensemble->courant = sauvegarde;
    }
}

void developpeAdditionNoeud(const Noeud *noeud1, const Noeud *noeud2, Noeud ** noeudDev)
{
  if(noeud1->operande == addition)
    {
      prems_Ens(noeud1->ensemble);
      while(noeud1->ensemble->courant != NULL)
	{
	  developpeAdditionNoeud(getData_Ens(noeud1->ensemble), noeud2, noeudDev);
	  suivant_Ens(noeud1->ensemble);
	}
    }
  else if(noeud2->operande == addition)
    {
      prems_Ens(noeud2->ensemble);
      while(noeud2->ensemble->courant != NULL)
	{
	  developpeAdditionNoeud(noeud1, getData_Ens(noeud2->ensemble), noeudDev);
	  suivant_Ens(noeud2->ensemble);
	}
    }
  else
    {
      Noeud *noeudTmp = NULL;
      operandeNoeud(noeud1, noeud2, &noeudTmp, multiplication);
      insert_Ens((*noeudDev)->ensemble, noeudTmp, NULL);
    }    
}

int verificationProduitNoeud(const Noeud *noeud)
{
  if(noeud->operande == multiplication)
    {
      int ret;
      prems_Ens(noeud->ensemble);
      while(noeud->ensemble->courant != NULL)
	{
	  ret = verificationAdditionNoeud(getData_Ens(noeud->ensemble));
	  if(ret == 0)
	    return 0;
	  suivant_Ens(noeud->ensemble);
	}
      return 1;
    }
  return 0;
}

int verificationAdditionNoeud(const Noeud *noeud)
{
  if(noeud->operande == valeur)
    return 1;
  else if(noeud->operande == addition)
    {
      prems_Ens(noeud->ensemble);
      while(noeud->ensemble->courant != NULL)
	{
	  if(verificationAdditionNoeud(getData_Ens(noeud->ensemble)) == 0)
	    return 0;
	  suivant_Ens(noeud->ensemble);
	}
      return 1;
    }
  return 0;
}
